package com.mid;

/**
 * Created by Lxk on 2019/9/13.
 */
public class Solution739 {

    public int[] dailyTemperatures(int[] T) {
        if (T == null || T.length == 0) {
            return null;
        }
        // 存放给定数据的最新位置
        int bucket[] = new int[71];
        for (int i = 0; i < bucket.length; i++) {
            bucket[i] = -1;
        }
        int res[] = new int[T.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = Integer.MAX_VALUE;
        }
        int dup[] = new int[res.length];
        for (int i = 0; i < dup.length; i++) {
            dup[i] = 0;
        }
        for (int i = 0; i < T.length; i++) {
            // 对应bucket中的位置
            int curPos = T[i] - 30;
            if (bucket[curPos] != -1) {
                dup[bucket[curPos]] = i - bucket[curPos];
            }
            bucket[curPos] = i;

            for (int k = curPos - 1; k >= 0; k--) {
                if (bucket[k] != -1 && bucket[curPos] - bucket[k] < res[bucket[k]]) {
                    res[bucket[k]] = bucket[curPos] - bucket[k];
                }
            }
        }
        for (int i = res.length - 1; i >= 0; i--) {
            if (Integer.MAX_VALUE != res[i]) {
                break;
            } else {
                res[i] = 0;
            }
        }
        for (int i = 0; i < dup.length; i++) {
            if (dup[i] != 0 && res[i] == Integer.MAX_VALUE) {
                int cur = i;
                int val = 0;
                while (dup[cur] != 0) {
                    val += dup[cur];
                    cur += dup[cur];
                }
                res[i] = res[cur] + val;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] temperatures = {89, 62, 70, 58, 47, 47, 46, 76, 100, 70};
        Solution739 solution739 = new Solution739();
        int[] res = solution739.dailyTemperatures(temperatures);
        System.out.println(res);

    }

}
